package dp;

import java.util.Scanner;

/**
 * 完全背包问题
 */
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main3 {
    public static int N = 1010;
    public static int n,V;
    public static int[] v = new int[N];
    public static int[] w = new int[N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();
            V = in.nextInt();
            for(int i = 1; i <= n; i++) {
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }
            //第一题
            // 1. 创建 dp 表
            // dp[i][j]表示：从前i个物品中选，总体积不超过j，所有选法中，最大的价值.
            int[][] dp = new int[n+1][V+1];
            // 2. 初始化
            // 3. 填表
            for(int i = 1; i <= n; i++) {
                for(int j = 0; j <= V; j++) {
                    dp[i][j] = dp[i-1][j];
                    if(j >= v[i]) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]] + w[i]);
                    }
                }
            }
            // 4. 返回值
            System.out.println(dp[n][V]);
            // 第二问           
            // 1. 创建 dp 表
            // dp[i][j]表示：从前i个物品选，总体积不超过j，所有选法中，最大的价值
            dp = new int[n+1][V+1];
            // 2. 初始化
            for(int j = 1; j <= V; j++) {
                dp[0][j] = -1;
            }
            // 3. 填表
            for(int i = 1; i <= n; i++) {
                for(int j = 0; j <= V; j++) {
                    dp[i][j] = dp[i-1][j];
                    if(j >= v[i] && dp[i][j-v[i]] != -1) {
                        dp[i][j] = Math.max(dp[i][j], dp[i][j-v[i]] + w[i]);
                    }
                }
            }
            // 4. 返回值
            System.out.println((dp[n][V] != -1) ? dp[n][V] : 0);
        }
    }
}

// 优化
class Main4 {
    public static int N = 1010;
    public static int n,V;
    public static int[] v = new int[N];
    public static int[] w = new int[N];
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextInt()) { // 注意 while 处理多个 case
            n = in.nextInt();
            V = in.nextInt();
            for(int i = 1; i <= n; i++) {
                v[i] = in.nextInt();
                w[i] = in.nextInt();
            }
            //第一题
            // 1. 创建 dp 表
            // dp[i][j]表示：从前i个物品中选，总体积不超过j，所有选法中，最大的价值.
            int[] dp = new int[V+1];
            // 2. 初始化
            // 3. 填表
            for(int i = 1; i <= n; i++) {
                for(int j = v[i]; j <= V; j++) {
                    dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
                }
            }
            // 4. 返回值
            System.out.println(dp[V]);
            // 第二问
            // 1. 创建 dp 表
            // dp[i][j]表示：从前i个物品选，总体积不超过j，所有选法中，最大的价值
            dp = new int[V+1];
            // 2. 初始化
            for(int j = 1; j <= V; j++) {
                dp[j] = -1;
            }
            // 3. 填表
            for(int i = 1; i <= n; i++) {
                for(int j = v[i]; j <= V; j++) {
                    if(dp[j-v[i]] != -1) {
                        dp[j] = Math.max(dp[j], dp[j-v[i]] + w[i]);
                    }
                }
            }
            // 4. 返回值
            System.out.println((dp[V] != -1) ? dp[V] : 0);
        }
    }
}